package sort;

import java.util.Arrays;

/**
 *
 * 堆排序：先使用批量建堆方式建堆，然后逐个移除顶元素。
 *
 * 最好时间复杂度：O(NlogN)
 * 时间复杂度：O(NlogN)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 敏感：不敏感，
 *
 */

public class HeapSort {

    private static int arr[] = { 3,5,1,10,6};

    public static void shiftDown(int parentIndex,int size){
        int childIndex = parentIndex * 2 + 1 ;
        while (childIndex < size){
            if(childIndex + 1 < size && arr[childIndex] > arr[childIndex+1]){
                childIndex++;
            }
            if(arr[parentIndex] > arr[childIndex]){
                swap(parentIndex, childIndex);
                parentIndex = childIndex;
                childIndex = parentIndex * 2 + 1 ;
            }else {
                break;
            }
        }
    }

    public static void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        for (int i = (arr.length-2) / 2; i >= 0; i--) {
            shiftDown(i, arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(0, i);
            shiftDown(0,i );
        }


        System.out.println(Arrays.toString(arr));


    }
}
